import java.util.ArrayList;
import java.util.List;

public class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        combinationSumHelper(k, n, 1, 0);
        return result;
    }
    private void combinationSumHelper(int k, int n, int startIndex, int sum){
        if(path.size() > k || sum > n){
            return;
        }
        if(path.size() == k && sum == n){
            result.add(new ArrayList<>(path));
            return;
        }
        //path.size() : 已经找个的个数
        //k - path.size() : 还需要找的个数
        //因此i到n至少要有 k - path.size()个数才有可能有结果，即 n - i + 1 >=  k - path.size()
        for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){
            path.add(i);

            combinationSumHelper(k, n, i+1, sum + i);
            path.remove(path.size() - 1);
        }
    }
}
